// const tree = {
//     val: 'a',
//     children: [
//         {
//             val: 'b',
//             children: [
//                 {
//                     val: 'd',
//                     children: []
//                 },
//                 {
//                     val: 'e',
//                     children: []
//                 }
//             ]
//         },
//         {
//             val: 'c',
//             children: [
//                 {
//                     val: 'f',
//                     children: []
//                 },
//                 {
//                     val: 'g',
//                     children: []
//                 }
//             ]
//         }
//     ]
// }

// // const dfs = (root) => {
// //     console.log(root.val);
// //     root.children.forEach(dfs);
// // }

// // dfs(tree)
// const bfs = (root) => {
//     const q = [root];
//     while (q.length > 0) {
//         const n = q.shift()
//         console.log(n.val)
//         n.children.forEach(child => {
//             q.push(child) 
//         });
//     }
// }

// bfs(tree)

// const tree = {
//     val: 1,
//     left: {
//         val: 2,
//         left: {
//             val: 4,
//             left: null,
//             right: null
//         },
//         right: {
//             val: 5,
//             left: null,
//             right: null
//         }
//     },
//     right: {
//         val: 3,
//         left: {
//             val: 6,
//             left: null,
//             right: null
//         },
//         right: {
//             val: 7,
//             left: null,
//             right: null    
//         }
//     }
// }

// const preorder = (root) => {
//     if(!root) return
//     // console.log(root.val)
//     preorder(root.left)
//     preorder(root.right)
//     console.log(root.val)
// }

// preorder(tree)

// const graph = {
//     0: [1, 2],
//     1: [2],
//     2: [0, 3],
//     3: [3]
// };

// const dfs = (n) => {
//     const p = [2]
//     const visited = new Set()
//     visited.add(2)
//     while(p.length){
//         const n = p.shift()
//         console.log(n)
//         graph[n].forEach(element => {
//             if(!visited.has(element)){
//                 p.push(element)
//                 visited.add(element)
//             }
//         });
//     }
// }

// dfs(2)

// const visited = new Set()
// const dfs = (n) => {
//     console.log(n);
//     visited.add(n);
//     graph[n].forEach(c => {
//         if(!visited.has(c)){
//             dfs(c)
//         }
//     })
// }

// dfs(2)

// 最小堆
// class MinHeap {
//     constructor() {
//         this.heap = []
//     }

//     /**
//      * 插入
//      * 将值插入堆的底部，即数组的末尾,然后上移,将这个值和它的父节点进行交换，直到父节点小于等于这个插入的值
//      * 大小为 k 的堆中插入元素的时间复杂度为O(logk)
//      **/
//     insert(value) {
//         this.heap.push(value);
//         this.shiftUp(this.heap.length - 1)
//     }

//     /**
//      * 删除堆顶:
//      * 1：用数组尾部元素替换堆顶(直接删除堆顶会破坏堆结构)
//      * 2：然后下移，将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
//      * 大小为 k 的堆中删除堆顶的时间复杂度为 O(logk)
//      */
//     pop(){
//         this.heap[0] = this.heap.pop();
//         this.shiftDown(0)
//     }

//     //获取堆顶
//     peek(){
//         return this.heap[0]
//     }

//     //获取堆大小
//     size() {
//         return this.heap.length
//     }

//     // 上移操作
//     shiftUp(index) {
//         if(index == 0) return; // 如果操作的元素为堆顶，禁止上移
//         const parentIndex = this.getParentIndex(index); // 获取父节点索引
//         if(this.heap[parentIndex] > this.heap[index]){  // 如果 父节点的值大于传入的子节点，需要交换父子节点
//             this.swap(parentIndex, index) // 交换父子节点
//             this.shiftUp(parentIndex) // 继续上移，因为已经上移过一次了，所以节点的索引变成了父节点的索引
//         }
//     }

//     // 下移操作
//     shiftDown(index) {
//         const leftIndex = this.getLeftIndex(index)
//         const rightIndex = this.getRigthIndex(index)
//         if(this.heap[leftIndex] < this.heap[index]){
//             this.swap(leftIndex, index)
//             this.shiftDown(leftIndex)
//         }
//         if(this.heap[rightIndex] < this.heap[index]){
//             this.swap(rightIndex, index)
//             this.shiftDown(rightIndex)
//         }
//     }

//     // 获取父节点索引
//     getParentIndex(i){
//         // return Math.floor((i - 1) / 2)
//         // 表示按把二进制数往右移一位，与 Math.floor((i - 1) / 2) 效果等同
//         return (i - 1) >> 1
//     }

//     // 获取左子节点索引
//     getLeftIndex(i){
//         return i * 2 + 1
//     }

//     // 获取右子节点索引
//     getRigthIndex(i){
//         return i * 2 + 2
//     }

//     // 交换两个节点的值
//     swap(i1, i2){
//         [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
//     }

// }

// const h = new MinHeap();
// debugger
// h.insert(3)
// h.insert(2)
// h.insert(1)
// h.pop()

// Array.prototype.bubbleSort = function () {
//     for(let i = 0; i < this.length - 1; i++){
//         for(let y = 0; y < this.length - 1 - i; y++){
//             if(this[y] < this[y + 1]){
//                 [this[y], this[y + 1]] = [this[y + 1], this[y]]
//             }
//         }
//     }
// }

// Array.prototype.bubbleSort = function () {
//     for(let i = 0; i < this.length - 1; i++){
//         let min = this[i]
//         for(let y = i; y < this.length; y++) {
//             if(this[y] < this[i]){
//                 [this[y],this[i]] = [this[i],this[y]]
//             }
//         }
//     }
// }

// Array.prototype.insertionSort = function () {
//     for(let i = 1; i < this.length; i++){
//         const temp = this[i]
//         let j = i
//         while (j > 0) {
//             if (this[j - 1] > temp) {
//                 this[j] = this[j - 1]
//             } else {
//                 break;
//             }
//             j -= 1
//         }
//         this[j] = temp
//     }
// }

// Array.prototype.mergeSort = function () {
//     for(let i = 1; i < this.length; i++){
//         const temp = this[i]
//         let j = i
//         while (j > 0) {
//             if (this[j - 1] > temp) {
//                 this[j] = this[j - 1]
//             } else {
//                 break;
//             }
//             j -= 1
//         }
//         this[j] = temp
//     }
// }

// arr = [1,23,421,11,23,4]
// arr.insertionSort()
// console.log(arr)

// Array.prototype.sequentialSearch = function (item) {
//    if(!item) return -1
//    let low = 0
//    let high = this.length - 1
//    while (low <= high) {
//        const mid = Math.floor((high + low) / 2)
//        const element = this[mid]
//        if(element < item){
//             low = mid + 1
//        } else if(element > item){
//             high = mid - 1
//        } else{
//            return mid 
//        }
//    }
//    return -1
// }

// arr = [1,2,3,4,5]

// console.log(arr.sequentialSearch(1))

// class Adaptee {
//     specificRequest () {
//         return '旧接口'
//     }
// }

// class Target {
//     constructor(){
//         this.adaptee = new Adaptee()
//     }
//     request() {
//         let info = this.adaptee.specificRequest()
//         return info
//     }
// }

// let target = new Target()
// console.log(target.request())

class Circle{
    draw(){
        console.log('画一个圆形')
    }
}

class Decorator {
    constructor(circle){
        this.circle = circle
    }
    draw(){
        this.circle.draw()
        this.setRedBorder(circle)
    }
    setRedBorder(circle){
        console.log('设置红色边框')
    }
}

let circle = new Circle()
circle.draw()

let dec = new Decorator(circle)
dec.draw()